718C - Sasha and Array - CodeForces Solution

#include <bits/stdc++.h>
#define _c const
#define _r register
#define ALL(x) x.begin(), x.end()
using namespace std;
_c int64_t mod = 1e9 + 7;
struct mat {
  int64_t _[2][2];
  mat(int64_t _00 = 0LL, int64_t _01 = 0LL, int64_t _10 = 0LL, int64_t _11 = 0LL) {
    _[0][0] = _00 % mod, _[0][1] = _01 % mod, _[1][1] = _11 % mod, _[1][0] = _10 % mod;
  }
  ~mat() {}
  int64_t *operator[](size_t x) { return this->_[x]; }
  friend mat operator+(mat x, mat y) {
    return mat((x[0][0] + y[0][0]) % mod, (x[1][0] + y[1][0]) % mod,
               (x[0][1] + y[0][1]) % mod, (x[1][1] + y[1][1]) % mod);
  }
  friend mat operator*(mat x, mat y) {
    return mat ((x[0][0] * y[0][0] + x[0][1] * y[1][0]) % mod, (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % mod,
                (x[1][0] * y[0][0] + x[1][1] * y[1][0]) % mod, (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % mod);
  }
  friend mat operator+=(mat &x, mat y) { return x = x + y; }
  friend mat operator*=(mat &x, mat y) { return x = x * y; }
};
inline mat qick_power(mat x, int32_t y) {
  mat ans = mat(1, 0, 0, 1);
  while (y) {
    if (y & 1) { ans *= x; }
    x *= x;
    y >>= 1;
  }
  return ans;
}
class Segment_tree {
private:
  struct Node {
    size_t left, right, length;
    mat laz_mul, value;
    Node *left_son, *right_son;
    Node () {
      left = right = length = 0U;
      laz_mul = value = mat(1, 0, 0, 1);
      left_son = right_son = nullptr;
    } 
    ~Node () {
      if (left_son != nullptr) { left_son->~Node(); }
      if (right_son != nullptr) { right_son->~Node(); }
      delete this;
    }
    
    inline void build(size_t left, size_t right, int32_t *val) {
      this->left = left, this->right = right, this->length = right - left + 1;
      if (left == right) {
        this->value = qick_power(mat(0, 1, 1, 1), val[left] + 1);
        return void (0);
      }
      size_t mid = left + (right - left >> 1);
      this->left_son = new Node, this->left_son->build(left, mid, val);
      this->right_son = new Node, this->right_son->build(mid + 1, right, val);
      this->value = this->left_son->value + this->right_son->value;
    }
    inline void laz_push_down() {
      this->left_son->laz_mul *= this->laz_mul;
      this->left_son->value *= this->laz_mul;
      this->right_son->laz_mul *= this->laz_mul;
      this->right_son->value *= this->laz_mul;
      this->laz_mul = mat (1, 0, 0, 1);
    }
    inline void modify_mul(size_t left, size_t right, mat &val) {
      if (right < this->left || this->right < left) { return void (0); }
      if (left <= this->left && this->right <= right) {
        this->laz_mul *= val;
        this->value *= val;
        return void (0);
      }
      laz_push_down();
      this->left_son->modify_mul(left, right, val);
      this->right_son->modify_mul(left, right, val);
      this->value = this->left_son->value + this->right_son->value;
    }
    inline mat query(size_t left, size_t right) {
      if (right < this->left || this->right < left) { return mat(); }
      if (left <= this->left && this->right <= right) { return this->value; }
      laz_push_down();
      return this->left_son->query(left, right) + this->right_son->query(left, right);
    }
  };
protected:
  Node *tree;

public:
  inline void build(size_t n, int32_t *val) {
    tree = new Node;
    tree->build(1U, n, val);
  }
  inline void modify_add(size_t left, size_t right, int32_t val) {
    mat _val = qick_power(mat(0, 1, 1, 1), val);
    tree->modify_mul(left, right, _val);
  }
  inline int64_t query(size_t left, size_t right) {
    return tree->query(left, right)[0][0];
  }
} tree;
int32_t n, m;
int32_t inp[100005];
inline void solve() {
  scanf("%d %d", &n, &m);
  for (size_t i = 1; i <= n; i++) { scanf("%d", inp + i); }
  tree.build(n, inp);
  while (m--) {
    size_t opt, l, r;
    scanf("%u %u %u", &opt, &l, &r);
    if (opt == 1) {
      int32_t val;
      scanf("%d", &val);
      tree.modify_add(l, r, val);
    }
    if (opt == 2) {
      printf("%lld\n", tree.query(l, r));
    }
  }
}
signed main() {
  solve();
  return 0;
}